package org.zhs.heap;

/**
 * @Author: zhs
 * @Date: 2024/5/16 22:11
 * @Version: 1.0
 * @Description: 二叉堆
 *
 * 堆 就是 一个被完全填满的 二叉树(完全二叉树)。
 *
 * 完全二叉树：
 *  1. 所有的层都是完全填满的，除了可能的最后一层。
 *  2. 最后一层的节点如果不是完全填满的，则所有的节点都集中在左侧。
 *
 *  **** 因为完全二叉树如此的有规律，那么我们可以使用数组来表示，而不是需要链接的链表
 *
 * 在一个完全二叉树中，如果给每个节点按照层序遍历编号（通常从1开始编号），那么对于任意节点i，它的父节点、左子节点和右子节点的编号将满足以下关系：
 *  1. 父节点的编号为 i/2（如果i是偶数，则父节点编号为i/2；如果i是奇数，则父节点编号为(i-1)/2）。
 *  2. 左子节点的编号为 2i。
 *  3. 右子节点的编号为 2i + 1。
 *  可以参考下面这个数组：
 *  [ , A,B,C,D,E,F,G,H,I ]
 *  其中数组0是空，因为通常从1开始。 其中A的左儿子为  2i(那么它的下标就是2=B)，它的右儿子为 2i+1(下标就是 3=C)，以此类推。。。。。。
 *
 *
 * 堆序性质：
 *  让操作快速执行的性质是 堆序性质。
 *  由于我们想快速找到最小元，那么最小元应该在根上。
 *  如果我们考虑任意子树也应该是一个堆，那么任意节点就应该小于它的所有子节点。
 *
 * ***************************************
 * ***************************************
 * 需要特别注意的是，完全二叉树是无序的！！！！！！！那么二叉堆也是无序的（二叉堆提供的是一个优先级，通过在插入时判断当前节点的根节点是不是比自己小，如果不是需要调整）。
 * 完全二叉树就是一个二叉树是无序的！！！！！如果不能理解这个的话，就无法理解二叉堆
 * 完全二叉树的插入顺序为，先插满当前层级。如果是子树的话，从左边依次开始插入，直接当前层级插满。
 *
 *
 */
public class BinaryHeap<E> {

    /**
     * 存放数据的数组
     * 因为完全二叉树可以使用数组来表示
     */
    private Object[] dataArray;

    /**
     * 默认的数组大小
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 当前数组大小
     */
    private int currentSize;

    public BinaryHeap(){
        this.dataArray =  new Object[DEFAULT_CAPACITY];
    }

    public BinaryHeap(int capacity){
        this.dataArray = new Object[capacity];
    }




}
